//===----------------------------------------------------------------------===//
//
//                         CMU-DB Project (15-445/645)
//                         ***DO NO SHARE PUBLICLY***
//
// Identification: src/page/b_plus_tree_leaf_page.cpp
//
// Copyright (c) 2018, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#include <cstring>
#include <sstream>
#include <utility>

#include "common/exception.h"
#include "common/macros.h"
#include "common/rid.h"
#include "storage/page/b_plus_tree_leaf_page.h"
#include "storage/page/b_plus_tree_page.h"

namespace bustub {

/*****************************************************************************
 * HELPER METHODS AND UTILITIES
 *****************************************************************************/

/**
 * Init method after creating a new leaf page
 * Including set page type, set current size to zero, set next page id and set max size
 */
INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::Init(int max_size) {
  SetPageType(IndexPageType::LEAF_PAGE);
  SetMaxSize(max_size);
  SetSize(0);
  SetNextPageId(INVALID_PAGE_ID);
}

/**
 * Helper methods to set/get next page id
 */
INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::GetNextPageId() const -> page_id_t { return next_page_id_; }

INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::SetNextPageId(page_id_t next_page_id) { next_page_id_ = next_page_id; }

/*
 * Helper method to find and return the key associated with input "index"(a.k.a
 * array offset)
 */
INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::KeyAt(int index) const -> KeyType {
  // replace with your own code
  BUSTUB_ASSERT(index < GetMaxSize(), "B_PLUS_TREE_LEAF_PAGE_TYPE::KeyAt index overflow");
  return array_[index].first;
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::ValueAt(int index) const -> ValueType {
  BUSTUB_ASSERT(index < GetMaxSize(), "B_PLUS_TREE_LEAF_PAGE_TYPE::ValueAt index overflow");
  return array_[index].second;
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::At(int index) const -> const MappingType & {
  BUSTUB_ASSERT(index < GetSize(), "wrong index");
  return array_[index];
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::Search(KeyType key, KeyComparator &comparator) const -> int {
  int mid = -1;
  int start = 0;
  int end = this->GetSize() - 1;
  while (start < end) {
    mid = (start + end) / 2;
    if (comparator(key, array_[mid].first) != -1) {
      start = mid + 1;
    } else {
      end = mid;
    }
  }
  BUSTUB_ASSERT(start == end, "start != end");
  return comparator(key, array_[start].first) == -1 ? start : -1;
}

INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::Insert(int pos, const KeyType &key, const ValueType &value) {
  BUSTUB_ASSERT(GetSize() < GetMaxSize(), "page is full!");
  for (int i = GetSize(); i >= pos + 1; i--) {
    array_[i] = array_[i - 1];
  }
  array_[pos] = std::make_pair(key, value);
  this->IncreaseSize(1);
}

INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::PushBack(const KeyType &key, const ValueType &value) {
  array_[this->GetSize()] = std::make_pair(key, value);
  this->IncreaseSize(1);
}

INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::Delete(const KeyType &key, const KeyComparator &comparator) {
  // 二分查找
  int mid = -1;
  int start = 0;
  int end = GetSize();
  while (start < end) {
    mid = (start + end) / 2;
    if (comparator(key, array_[mid].first) != -1) {
      start = mid + 1;
    } else {
      end = mid;
    }
  }
  BUSTUB_ASSERT(start == end, "start != end");
  start--;
  BUSTUB_ASSERT(start >= 0, "节点中不存在要删除的key");
  BUSTUB_ASSERT(comparator(key, array_[start].first) == 0, "节点中不存在要删除的key");
  for (int i = start; i < GetSize() - 1; ++i) {
    array_[i] = array_[i + 1];
  }
  this->IncreaseSize(-1);
}

INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::Delete(int index) {
  if (index < 0 || index >= this->GetSize()) {
    throw bustub::Exception("index越界");
  }
  for (; index < this->GetSize() - 1; ++index) {
    array_[index] = array_[index + 1];
  }
  IncreaseSize(-1);
}
template class BPlusTreeLeafPage<GenericKey<4>, RID, GenericComparator<4>>;
template class BPlusTreeLeafPage<GenericKey<8>, RID, GenericComparator<8>>;
template class BPlusTreeLeafPage<GenericKey<16>, RID, GenericComparator<16>>;
template class BPlusTreeLeafPage<GenericKey<32>, RID, GenericComparator<32>>;
template class BPlusTreeLeafPage<GenericKey<64>, RID, GenericComparator<64>>;
}  // namespace bustub
